package algorithm.sort;

/**
 * 对int型使用位运算版本. 需要31次归并
 * </p>
 *
 * @author zhangbo
 * @since 1.0.0
 */
public class BitMerge extends Common implements Sort {
    QuickSort quickSort = new QuickSort(type);

    public void merge(int[] nums, int j, int len) {
        if (j > 32) {
            return;
        }

        // if (len <= 1) {
        // return;
        // }
        // if (len == 2) {
        // if (nums[0] > nums[1]) {
        // nums[0] = nums[0] ^ nums[1];
        // nums[1] = nums[0] ^ nums[1];
        // nums[0] = nums[0] ^ nums[1];
        // }
        // return;
        // }

        if (len < 33) {
            quickSort.quickSort(nums, 0, len - 1);
            return;
        }

        int[] rnums = new int[len];
        int[] lnums = new int[len];
        int r = 0;
        int l = 0;
        int pos = (1 << 32 - j);
        for (int i = 0; i < len; i++) {
            if ((nums[i] & pos) == pos) {
                rnums[r++] = nums[i];
            } else {
                lnums[l++] = nums[i];
            }
        }
        merge(lnums, j + 1, l);
        int i = 0;
        for (i = 0; i < l; i++) {
            nums[i] = lnums[i];
        }
        lnums = null;

        merge(rnums, j + 1, r);
        for (int k = 0; k < r; k++) {
            nums[k + i] = rnums[k];
        }
    }

    @Override
    public void execute(int[] nums) {
        execute(nums, this.type);
    }

    @Override
    public void execute(int[] nums, ImplementType methodType) {
        int maxIndex = 0;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > nums[maxIndex]) {
                maxIndex = i;
            }
        }
        int j = 1;
        for (; j < 32; j++) {
            if ((nums[maxIndex] & (1 << 32 - j)) >> (32 - j) == 1) {
                break;
            }
        }
        System.out.println(j);
        merge(nums, j, nums.length);
    }
}
